class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        
        vector<int> ans(10001,0);
        for(int x : nums){
            ans[x] += x;
        }
        
        vector<int> dp(10001,0);
        dp[1] = ans[1];
        
        for(int i = 2;i <= 10000;i++){
            dp[i] = max(dp[i-1],dp[i-2]+ans[i]);
        }
        return dp[10000];
    }
};
